package com.itheima.datastructure.linkedlist;


import java.util.Iterator;
import java.util.function.Consumer;

public class SinglyLinkedList implements Iterable<Integer>{//整体
    private  Node head=null;//头指针

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p=head;
            @Override
            public boolean hasNext() {
                return p!=null;
            }

            @Override
            public Integer next() {
                int v=p.value;
                p=p.next;
                return v;
            }
        };
    }

    //节点类
    private static class Node {
        int value; // 值
        Node next; // 下一个节点指针
        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    //向链表头部添加
    public void addFirst(int value) {
        // 1. 链表为空
        if (head==null){
            head = new Node(value, null);
        }else{
            // 2. 链表非空
            head = new Node(value, head);
        }
    }

    //遍历
    public void loop1(Consumer<Integer> consumer){
        Node p=head;
        while(p!=null){
            consumer.accept(p.value);
            p = p.next;
        }
    }

    public void loop2(Consumer<Integer> consumer){
        for(Node p=head;p!=null;p=p.next){
            consumer.accept(p.value);
        }
    }

    private Node findLast(){
        //空链表
        if(head==null){
            return null;
        }
        Node p;
        for(p=head;p.next!=null;p=p.next){

        }
        //找到最后一个节点
        return p;
    }

    public void addLast(int value){
        Node last=findLast();
        //如果是空节点
        if(last==null){
            addFirst(value);
            return;
        }
        //将原先最后一个节点添加新的节点
        last.next=new Node(value,null);
    }


    //索引
    /*public void test(){
        int i=0;
        for(Node p=head;p!=null;p=p.next,i++){
            System.out.println(p.value+"的索引是："+i);
        }
    }*/

    private Node findNode(int index){
        int i=0;
        for(Node p=head;p!=null;p=p.next,i++){
            if(i==index){
                return p;
            }
        }
        //没找到
        return null;
    }

    public int get(int index){
        Node node=findNode(index);
        if(node==null){
            throw Illegalindex(index);
        }
        return node.value;
    }

    private static IllegalArgumentException Illegalindex(int index) {
        return new IllegalArgumentException(
                String.format("index [%d] 不合法%n", index)
        );
    }

    //向索引位置插入
    public void insert(int index,int value){
        //index==0，本质是向链表头部插入节点
        if(index==0){
            addFirst(value);
            return;
        }
        //找打插入位置的上一个节点
        Node prev=findNode(index-1);
        if(prev==null){//找不到
            throw Illegalindex(index);
        }
        prev.next=new Node(value,prev.next);
    }

    public void removeFirst(){
        if (head==null){
            throw Illegalindex(0);
        }
        head=head.next;
    }

    public void removeLast(){
        int lastIndex=0;
        int prevIndex;
        int i=0;
        for(Node p=head;p!=null;p=p.next,i++){
            lastIndex=i;
        }
        prevIndex=lastIndex-1;
        if(lastIndex==0){
            head=null;
        }else{
            findNode(prevIndex).next=null;
        }
    }

    public void remove(int index){
        if(index==0){
            removeFirst();
        }
        Node prev=findNode(index-1);//上一个节点
        if (prev==null){
            throw Illegalindex(index);
        }
        Node removed=prev.next;//被删除的节点
        prev.next=removed.next;
    }

    public void loop3(){
       recursion(head);
    }

    private void recursion(Node curr){
        if(curr==null){
            return;
        }
        System.out.println("before:"+curr.value);
        recursion(curr.next);
        System.out.println("after:"+curr.value);
    }

}



